package dsg

import (
	"io"
	"fmt"
)

type LinkSet struct {
      size int
	last []int // -2: unset -1: head;
	next []int // -1: unset or tail
      head int
      tail int
      num    int
      clabel int
}

func InitLinkSet (size int) * LinkSet {
      var ls LinkSet
      ls.size = size
      ls.last = make ([]int, size)
      ls.next = make ([]int, size)
      ls.head = -1
      ls.tail = -1
      ls.num = 0
      ls.clabel = -1
      for i := 0; i < size; i ++ {
            ls.last[i] = -2
            ls.next[i] = -1
      }
      return &ls
}

func InitFullLinkSet (size int) * LinkSet {
      ls := InitLinkSet (size)
      ls.head = 0
      ls.tail = size - 1
      ls.num = size
      for i := 0; i < size; i ++ {
            ls.last[i] = i - 1
            ls.next[i] = i + 1
      }
      ls.next[size - 1] = -1
      return ls
}

func InverseLinkSet (ls * LinkSet) (ls_inv * LinkSet) {
	ls_inv = InitLinkSet (ls.size)
	for i := 0; i < ls.size; i ++ {
		if !ls.GetLabel (i) {
			ls_inv.Set (i)
		}
	}
	return 
}

func (ls * LinkSet) Expand (size int) {
	for i := 0; i < size; i ++ {
		ls.last = append (ls.last, -2)
		ls.next = append (ls.next, -1)
	}
	ls.size += size
}

func (ls * LinkSet) Set (ind int) {
      if (ls.last[ind] != -2) {return}
      ls.last[ind] = ls.tail
      if ls.tail == -1 {
            ls.head = ind
      } else {
            ls.next[ls.tail] = ind
      }
      ls.tail = ind
      ls.num ++ 
}

/* 如果要删除正在遍历的元素, 则首先自动调用一次 LSTraverseForward */
func (ls * LinkSet) UnSet (ind int) {
	if (ls.clabel == ind) {
		ls.TraverseForward()
	}
      if (ls.last[ind] == -2) {return}
      if (ls.next[ind] != -1) {
            ls.last[ls.next[ind]] = ls.last[ind]
      } else {
            ls.tail = ls.last[ind]
      }
      if (ls.last[ind] != -1) {
            ls.next[ls.last[ind]] = ls.next[ind]
      } else {
            ls.head = ls.next[ind]
      }
      ls.last[ind] = -2
      ls.next[ind] = -1
      ls.num --
}

func (ls * LinkSet) Clear () {
	for i := ls.head; i != -1; {
		ls.last[i] = -2
		i, ls.next[i] = ls.next[i], -1
	}

      ls.head = -1
      ls.tail = -1
      ls.num = 0
      ls.clabel = -1
}

func (ls * LinkSet) GetSize () int {
      return ls.size
}

func (ls * LinkSet) GetNum () int {
      return ls.num
}

func (ls * LinkSet) GetLabel (ind int) bool {
      if (ls.last[ind] == -2) {
            return false
      } else {
            return true
      }
}

func (ls * LinkSet) GetFirstLabel () int {
	return ls.head
}

func (ls * LinkSet) TraverseStart () {
      ls.clabel = ls.head
}

func (ls * LinkSet) TraverseEnd () {
      ls.clabel = ls.tail
}


func (ls * LinkSet) TraverseForward () {
      ls.clabel = ls.next[ls.clabel]
}

func (ls * LinkSet) TraverseBackward () {
      ls.clabel = ls.last[ls.clabel]
}

func (ls * LinkSet) DeleteCurrentTraverse () {
      ls.clabel = ls.next[ls.clabel]
      ls.UnSet (ls.clabel)
}

// return -1 if traverse to tail
func (ls * LinkSet) GetTraverseLabel () int {
      return ls.clabel
}

func (ls * LinkSet) GetAllLabel () []int {
      res := make ([]int, 0)
      
      for ls.TraverseStart () ;; ls.TraverseForward() {
            label := ls.GetTraverseLabel()
            if label == -1 {break}
            res = append (res, label)
      }
      return res
}

func (ls * LinkSet) Save (fout io.Writer) {
	fmt.Fprintf (fout, "%d %d\n", ls.size, ls.num)
	for ls.TraverseStart() ; ; ls.TraverseForward () {
		i := ls.GetTraverseLabel()
		if i == -1 {break}
		fmt.Fprintf (fout, "%d ", i)
	}
	fmt.Fprintf (fout, "\n")
}

func  LoadLinkSet (fin io.Reader) * LinkSet {
	var size, num int
	n, _ := fmt.Fscan (fin, &size, &num)
	if n != 2 {return nil}

	ls := InitLinkSet (size)

	for i := 0; i < num; i ++ {
		var ind int
		fmt.Fscan (fin, &ind)
		ls.Set (ind)
	}

	return ls
}

